package leetcode_zh

import (
	"container/heap"
	"math"
	"math/rand"
	sort2 "sort"
	"strconv"
	"strings"
)

/**
 * @Description: 32. 最长有效括号 困难
 * @Keyword: 动态规划
 * @Author: kami
 * @Date: 2022/6/4 18:07
 **/
func longestValidParentheses(s string) int {
	maxAns := 0
	dp := make([]int, len(s))
	for i := 1; i < len(s); i++ {
		if s[i] == ')' {
			if s[i-1] == '(' {
				if i >= 2 {
					dp[i] = dp[i-2] + 2
				} else {
					dp[i] = 2
				}
			} else if i-dp[i-1] > 0 && s[i-dp[i-1]-1] == '(' {
				if i-dp[i-1] >= 2 {
					dp[i] = dp[i-1] + dp[i-dp[i-1]-2] + 2
				} else {
					dp[i] = dp[i-1] + 2
				}
			}
			maxAns = getMax(maxAns, dp[i])
		}
	}
	return maxAns
}

/**
 * @Description: 32. 最长有效括号 困难
 * @Keyword: 栈
 * @Author: kami
 * @Date: 2022/6/4 20:35
 **/
func longestValidParentheses32(s string) int {
	maxAns := 0
	stack := []int{}
	stack = append(stack, -1)
	for i := 0; i < len(s); i++ {
		if s[i] == '(' {
			stack = append(stack, i)
		} else {
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				stack = append(stack, i)
			} else {
				maxAns = getMax(maxAns, i-stack[len(stack)-1])
			}
		}
	}
	return maxAns
}

/**
 * @Description: 39. 组合总和 中等
 * @Keyword: 回溯大法好
 * @Author: kami
 * @Date: 2022/6/5 13:07
 **/
func combinationSum(candidates []int, target int) [][]int {
	var result [][]int
	result = combinationHelper(candidates, []int{}, target, 0, 0, result)
	return result
}

func combinationHelper(candidates, path []int, target, sum, startIdx int, result [][]int) [][]int {
	if sum > target {
		return result
	}
	if sum == target {
		var res = make([]int, len(path))
		copy(res, path)
		result = append(result, res)
		return result
	}
	for i := startIdx; i < len(candidates); i++ {
		path = append(path, candidates[i])
		result = combinationHelper(candidates, path, target, sum+candidates[i], i, result)
		path = path[0 : len(path)-1]
	}
	return result
}

/*
*
  - @Description: 42. 接雨水 困难
  - @Keyword:  对于vector中每个点，水有多高取决于这个点左侧和右侧墙壁的最大高度。第一个for循环找每个点的左侧最大高度，
    第二个for循环找每个点右侧的最大高度，循环中跳过最左侧(i=0)和最右侧点(i=vector.size()-1)的原因是这两个点由于没有左侧墙壁或右侧墙壁
    所以最大墙壁高度肯定是0，故在初始化vector的时候已经将其默认设置成0了。在得到所有点的左右墙壁最大高度后，
    木桶原理取左右墙壁较低的那个高度减去当前位置墙壁作为地面的高度就得到了这个位置上水的高度。然后将所有点的水高度相加即为解。
  - @Author: kami
  - @Date: 2022/6/5 13:37
    *
*/
func trap(height []int) int {
	var n = len(height)
	// left[i]表示i左边的最大值，right[i]表示i右边的最大值
	var left = make([]int, n)
	var right = make([]int, n)
	for i := 1; i < n; i++ {
		left[i] = getMax(left[i-1], height[i-1])
	}
	for i := n - 2; i >= 0; i-- {
		right[i] = getMax(right[i+1], height[i+1])
	}
	var water int
	for i := 0; i < n; i++ {
		var level = getMin(left[i], right[i])
		water += getMax(0, level-height[i])
	}
	return water
}

/**
 * @Description: 48. 旋转图像 中等
 * @Keyword: 旋转90度 = 斜对角翻转 + 水平翻转
 * @Author: kami
 * @Date: 2022/6/7 17:16
 **/
func rotate(matrix [][]int) {
	m := len(matrix)
	n := len(matrix[0])
	// 斜对角翻转
	for i := 0; i < m; i++ {
		for j := 0; j < n-i; j++ {
			matrix[i][j], matrix[m-j-1][n-i-1] = matrix[m-j-1][n-i-1], matrix[i][j]
		}
	}
	// 上下翻转
	var halfM = m / 2
	for i := 0; i < halfM; i++ {
		for j := 0; j < n; j++ {
			matrix[i][j], matrix[m-i-1][j] = matrix[m-i-1][j], matrix[i][j]
		}
	}
}

/**
 * @Description: 146. LRU 缓存 中等
 * @Keyword: TODO
 * @Author: kami
 * @Date: 2022/6/11 6:52
 **/
type LRUCache struct {
	head     *Node1
	tail     *Node1
	cache    map[int]*Node1
	capacity int
}
type Node1 struct {
	key  int
	val  int
	pre  *Node1
	next *Node1
}

func ConstructorLRU(capacity int) LRUCache {
	return LRUCache{
		cache:    make(map[int]*Node1),
		capacity: capacity,
	}
}

func (this *LRUCache) Get(key int) int {
	if V, OK := this.cache[key]; OK {
		// 移动到头部
		this.moveToHeadNode1(V)
		return V.val
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if V, OK := this.cache[key]; OK {
		if V.val != value {
			V.val = value
		}
		// 移动到头部
		this.moveToHeadNode1(V)
		return
	}
	//如果已达到容量，则移除尾部
	if len(this.cache) == this.capacity {
		this.removeTail()
	}
	this.moveToHead(key, value)
}

func (this *LRUCache) moveToHead(key, value int) {
	curNode1 := &Node1{
		key: key,
		val: value,
	}
	this.moveToHeadNode1(curNode1)
}

func (this *LRUCache) moveToHeadNode1(Node1 *Node1) {
	// 新节点
	if Node1.pre == nil && Node1.next == nil {
		this.cache[Node1.key] = Node1
		if this.head == nil || this.tail == nil {
			this.head = Node1
			this.tail = Node1
			return
		}
		this.head.pre = Node1
		Node1.next = this.head
		this.head = Node1
		return
	}
	// 老节点
	// 头节点
	if Node1 == this.head {
		return
	}
	// 尾节点，节点数量>=2
	preNode1 := Node1.pre
	nextNode1 := Node1.next
	preNode1.next = nextNode1
	if nextNode1 != nil {
		nextNode1.pre = preNode1
	} else {
		// 尾节点更新
		this.tail = preNode1
	}
	this.head.pre = Node1
	Node1.next = this.head
	this.head = Node1

	return
}

func (this *LRUCache) removeTail() {
	if this.tail == nil || this.head == nil {
		return
	}
	delete(this.cache, this.tail.key)
	// 只有一个节点
	if this.tail.pre == nil || this.head.next == nil {
		this.head = nil
		this.tail = nil
		return
	}
	// 多个节点
	this.tail = this.tail.pre
	this.tail.next = nil

	return
}

/**
 * @Description: 347. 前 K 个高频元素 中等
 * @Keyword: 小顶堆
 * @Author: kami
 * @Date: 2022/6/11 9:30
 **/
func topKFrequentHeap(nums []int, k int) []int {
	occurrences := map[int]int{}
	for _, num := range nums {
		occurrences[num]++
	}
	h := &IHeap{}
	heap.Init(h)
	for key, value := range occurrences {
		// 数值，出现次数
		heap.Push(h, [2]int{key, value})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	ret := make([]int, k)
	for i := 0; i < k; i++ {
		ret[k-i-1] = heap.Pop(h).([2]int)[0]
	}
	return ret
}

type IHeap [][2]int

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/**
 * @Description: 239. 滑动窗口最大值 困难
 * @Keyword: 滑动窗口
 * @Author: kami
 * @Date: 2022/6/11 17:10
 **/
func maxSlidingWindow(nums []int, k int) []int {
	var win []int
	var res []int
	for i := 0; i < len(nums); i++ {
		// 如果的左边界为窗口最大值
		if i >= k && win[0] <= i-k {
			win = win[1:]
		}
		var size = len(win)
		for size > 0 && nums[win[size-1]] <= nums[i] {
			win = win[:size-1]
			size--
		}
		win = append(win, i)

		if i >= k-1 {
			res = append(res, nums[win[0]])
		}
	}
	return res
}

/*
*
  - @Description: 461. 汉明距离 简单
  - @Keyword: 当一个数被减1时，他最右边的那个值为1的Bit将变为0，同时其右边的所有的Bit都会变成1
    位与并赋值操作。去掉已经被计数过的1，并将改值重新设置给n.
  - @Author: kami
  - @Date: 2022/6/12 13:03
    *
*/
func hammingDistance(x int, y int) int {
	var n = x ^ y
	var count = 0
	for n > 0 {
		count++
		n &= n - 1
	}
	return count
}

/**
 * @Description: 739. 每日温度 中等
 * @Keyword: 暴力遍历
 * @Author: kami
 * @Date: 2022/6/14 11:42
 **/
func dailyTemperatures(temperatures []int) []int {
	var res []int
	for i := 0; i < len(temperatures); i++ {
		var day int
		for j := i + 1; j < len(temperatures); j++ {
			if temperatures[j] > temperatures[i] {
				day = j - i
				break
			}
		}
		res = append(res, day)
	}
	return res
}

/**
 * @Description: 739. 每日温度 中等
 * @Keyword: 寻找右边第一个大的值,从后往前计算
 * @Author: kami
 * @Date: 2022/6/14 11:42
 **/
func dailyTemperatures739(temperatures []int) []int {
	var res = make([]int, len(temperatures))
	res[len(temperatures)-1] = 0
	for i := len(temperatures) - 2; i >= 0; i-- {
		for j := i + 1; j < len(temperatures); j += res[j] {
			if temperatures[i] < temperatures[j] {
				res[i] = j - i
				break
			} else if res[j] == 0 {
				res[i] = 0
				break
			}
		}
	}
	return res
}

/**
 * @Description: 494. 目标和 中等
 * @Keyword: 动态规划，假设 target = sum(N) - sum(P),一部分子集为正，一部分子集为负，sum = sum(N) + sum(P)得到 sum(P) = (sum-target )/ 2 为非负偶数
 * @Author: kami
 * @Date: 2022/6/17 12:20
 **/
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	diff := sum - target
	// diff为非负偶数
	if diff < 0 || diff%2 == 1 {
		return 0
	}
	// neg为 符号为负号的子集即sum(P)
	n, neg := len(nums), diff/2
	// dp[i][j] 为 在数组nums的前 i 个数中选取元素，使得这些元素之和等于 j 的方案数
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, neg+1)
	}
	// 前0个数字中和为0的数量1个
	dp[0][0] = 1
	for i, num := range nums {
		for j := 0; j <= neg; j++ {
			// 和为j的和前面一个相同
			dp[i+1][j] = dp[i][j]
			// 日机票
			if j >= num {
				dp[i+1][j] += dp[i][j-num]
			}
		}
	}
	return dp[n][neg]
}

/**
 * @Description: 79. 单词搜索 中等
 * @Keyword: 回溯，同层只能下或右，下层可左，右，下
 * @Author: kami
 * @Date: 2022/6/18 10:18
 **/
func exist(board [][]byte, word string) bool {
	var used = make([][]bool, len(board))
	for i := 0; i < len(board); i++ {
		used[i] = make([]bool, len(board[0]))
	}

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if backTrackBoard(board, used, word, 0, i, j) {
				return true
			}
		}
	}
	return false
}

func backTrackBoard(board [][]byte, used [][]bool, word string, wordIdx, mIdx, nIdx int) bool {
	// 下标越界,或者已使用,或者字母不同
	if wordIdx >= len(word) || mIdx < 0 || nIdx < 0 || mIdx == len(board) || nIdx == len(board[0]) ||
		used[mIdx][nIdx] || board[mIdx][nIdx] != word[wordIdx] {
		return false
	}
	// 字符串最后一位与列表相同，并且没有使用过
	if board[mIdx][nIdx] == word[wordIdx] && wordIdx == len(word)-1 {
		return true
	}
	// 上下左右回溯
	used[mIdx][nIdx] = true
	// 上
	var up = backTrackBoard(board, used, word, wordIdx+1, mIdx-1, nIdx)
	// 下
	var down = backTrackBoard(board, used, word, wordIdx+1, mIdx+1, nIdx)
	// 左
	var left = backTrackBoard(board, used, word, wordIdx+1, mIdx, nIdx-1)
	// 右
	var right = backTrackBoard(board, used, word, wordIdx+1, mIdx, nIdx+1)
	used[mIdx][nIdx] = false
	return up || down || left || right
}

/**
 * @Description: 49. 字母异位词分组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/19 14:32
 **/
func groupAnagrams(strs []string) [][]string {
	mp := map[string][]string{}
	for _, str := range strs {
		s := []byte(str)
		sort2.Slice(s, func(i, j int) bool { return s[i] < s[j] })
		sortedStr := string(s)
		mp[sortedStr] = append(mp[sortedStr], str)
	}
	ans := make([][]string, 0, len(mp))
	for _, v := range mp {
		ans = append(ans, v)
	}
	return ans
}

/**
 * @Description: 75. 颜色分类 中等
 * @Keyword: 0、 1 和 2 分别表示红色、白色和蓝色
 * @Author: kami
 * @Date: 2022/6/20 11:59
 **/
func sortColors(nums []int) {
	var zeroCnt int
	var oneCnt int
	for _, num := range nums {
		switch num {
		case 0:
			zeroCnt++
		case 1:
			oneCnt++
		}
	}
	var twoCnt = len(nums) - zeroCnt - oneCnt
	var idx int
	for idx < len(nums) {
		if zeroCnt > 0 {
			nums[idx] = 0
			zeroCnt--
			idx++
			continue
		}
		if oneCnt > 0 {
			nums[idx] = 1
			oneCnt--
			idx++
			continue
		}
		if twoCnt > 0 {
			nums[idx] = 2
			twoCnt--
			idx++
			continue
		}
	}

}

/**
 * @Description: 78. 子集 中等
 * @Keyword: 回溯
 * @Author: kami
 * @Date: 2022/6/20 12:11
 **/
func subsets(nums []int) [][]int {
	var res = [][]int{{}}
	var subsetsDfs func(nums, curRes []int, idx int)
	subsetsDfs = func(nums, curRes []int, idx int) {
		if idx == len(nums) {
			return
		}
		curRes = append(curRes, nums[idx])
		var copyCur = make([]int, len(curRes))
		copy(copyCur, curRes)
		res = append(res, copyCur)
		subsetsDfs(nums, curRes, idx+1)
		curRes = curRes[0 : len(curRes)-1]
		subsetsDfs(nums, curRes, idx+1)
	}
	subsetsDfs(nums, []int{}, 0)
	return res
}

/**
 * @Description: 152. 乘积最大子数组 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/20 12:41
 **/
func maxProduct(nums []int) int {
	var max = math.MinInt
	var imax = 1
	var imin = 1 //一个保存最大的，一个保存最小的。
	for i := 0; i < len(nums); i++ {
		//如果数组的数是负数，那么会导致最大的变最小的，最小的变最大的。因此交换两个的值。
		if nums[i] < 0 {
			var tmp = imax
			imax = imin
			imin = tmp
		}
		imax = getMax(imax*nums[i], nums[i])
		imin = getMin(imin*nums[i], nums[i])

		max = getMax(max, imax)
	}
	return max
}

/**
 * @Description: 200. 岛屿数量 中等
 * @Keyword: 回溯
 * @Author: kami
 * @Date: 2022/6/21 14:24
 **/
func numIslands(grid [][]byte) int {

	var infect func(grid [][]byte, mIdx, nIdx int)
	infect = func(grid [][]byte, mIdx, nIdx int) {
		if mIdx < 0 || mIdx >= len(grid) ||
			nIdx < 0 || nIdx >= len(grid[0]) || grid[mIdx][nIdx] != '1' {
			return
		}
		grid[mIdx][nIdx] = '2'
		// 上
		infect(grid, mIdx-1, nIdx)
		// 下
		infect(grid, mIdx+1, nIdx)
		// 左
		infect(grid, mIdx, nIdx-1)
		// 右
		infect(grid, mIdx, nIdx+1)
	}
	var cnt int
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				infect(grid, i, j)
				cnt++
			}
		}
	}
	return cnt
}

/**
 * @Description: 207. 课程表 中等
 * @Keyword: 有向无环图
 * @Author: kami
 * @Date: 2022/6/21 15:09
 **/
func canFinish(numCourses int, prerequisites [][]int) bool {
	var size = len(prerequisites)
	if size == 0 {
		return true
	}
	// 下标课程的前置课程数量
	var pointer = make([]int, numCourses)
	for i := 0; i < size; i++ {
		pointer[prerequisites[i][1]]++
	}
	// 下标课程是否被移除，移除代表可以完成该课程学习
	var removed = make([]bool, size)
	var remove int
	for remove < size {
		var curRemove int
		for i := 0; i < size; i++ {
			// 当前课程已完成
			if removed[i] {
				continue
			}
			// 当前课程的前置课程数量为0，则代表可以完成该课程
			if pointer[prerequisites[i][0]] == 0 {
				// 减少关联课程的前置课程数量
				pointer[prerequisites[i][1]]--
				removed[i] = true
				curRemove++
			}
		}
		// 如果一轮下来，一门课程也没移除，则返回
		if curRemove == 0 {
			return false
		}
		remove += curRemove
	}
	return true
}

/**
 * @Description: 208. 实现 Trie (前缀树) 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/21 17:27
 **/
type Trie struct {
	children [26]*Trie
	isEnd    bool
}

func ConstructorTrie() Trie {
	return Trie{}
}

func (t *Trie) Insert(word string) {
	node := t
	for _, ch := range word {
		ch -= 'a'
		if node.children[ch] == nil {
			node.children[ch] = &Trie{}
		}
		node = node.children[ch]
	}
	node.isEnd = true
}

func (t *Trie) SearchPrefix(prefix string) *Trie {
	node := t
	for _, ch := range prefix {
		ch -= 'a'
		if node.children[ch] == nil {
			return nil
		}
		node = node.children[ch]
	}
	return node
}

func (t *Trie) Search(word string) bool {
	node := t.SearchPrefix(word)
	return node != nil && node.isEnd
}

func (t *Trie) StartsWith(prefix string) bool {
	return t.SearchPrefix(prefix) != nil
}

/**
 * @Description: 621. 任务调度器 中等
 * @Keyword: 找公式 (maxCnt-1)*(n+1) + num，其中maxCnt是字母出现的最大次数，num是有多少个字母出现的次数是最大的
 * @Author: kami
 * @Date: 2022/6/25 14:05
 **/
func leastInterval(tasks []byte, n int) int {
	var cntByte = make([]int, 26)
	for i := 0; i < len(tasks); i++ {
		cntByte[tasks[i]-'A']++
	}
	var maxCnt int
	var num int
	for i := 0; i < 26; i++ {
		if cntByte[i] > maxCnt {
			maxCnt = cntByte[i]
			num = 1
			continue
		}
		if cntByte[i] == maxCnt {
			num++
		}
	}
	var res = (maxCnt-1)*(n+1) + num
	if len(tasks) > res {
		return len(tasks)
	}
	return res
}

/**
 * @Description: 240. 搜索二维矩阵 II 中等
 * @Keyword: 右上角往下
 * @Author: kami
 * @Date: 2022/6/25 18:18
 **/
func searchMatrix(matrix [][]int, target int) bool {
	x, y := 0, len(matrix[0])-1
	for x < len(matrix) && y >= 0 {
		if matrix[x][y] == target {
			return true
		}
		// 最右侧
		if matrix[x][y] > target {
			y--
		} else {
			x++
		}
	}
	return false
}

func binarySearch240(nums []int, target int) bool {
	var left int
	var right = len(nums) - 1
	for left <= right {
		var middle = (left + right) / 2
		if nums[middle] == target {
			return true
		} else if nums[middle] > target {
			left = middle + 1
		} else {
			right = middle - 1
		}
	}
	return false
}

/**
 * @Description: 416. 分割等和子集 中等
 * @Keyword: n数之和,动态规划
 * @Author: kami
 * @Date: 2022/6/25 19:09
 **/
func canPartition(nums []int) bool {
	var sum int
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	if sum&1 > 0 {
		return false
	}
	// dp[i]代表有没有组成这个数的
	var size = sum / 2
	var dp = make([]bool, size+1)
	for i := 0; i < len(nums); i++ {
		if nums[i] > size {
			return false
		}
		if nums[i] == size || dp[size-nums[i]] {
			return true
		}
		var co []int
		for j := 1; j <= size; j++ {
			if dp[j] {
				if j+nums[i] <= size && !dp[j+nums[i]] {
					co = append(co, j+nums[i])
				}
			}
		}
		for j := 0; j < len(co); j++ {
			dp[co[j]] = true
		}

		if !dp[nums[i]] {
			dp[nums[i]] = true
		}

	}
	return false
}

/**
 * @Description: 238. 除自身以外数组的乘积 中等
 * @Keyword:
 * @Author: kami
 * @Date: 2022/6/25 19:50
 **/
func productExceptSelf(nums []int) []int {
	if len(nums) < 2 {
		return nums
	}
	var size = len(nums)
	var preProduct = make([]int, size)
	preProduct[0] = nums[0]
	var postProduct = make([]int, size)
	postProduct[size-1] = nums[size-1]
	for i := 1; i < len(nums); i++ {
		preProduct[i] = preProduct[i-1] * nums[i]
		postProduct[size-i-1] = postProduct[size-i] * nums[size-i-1]
	}
	var res = make([]int, size)
	res[size-1] = preProduct[size-2]
	res[0] = postProduct[1]
	for i := 1; i < size-1; i++ {
		res[i] = preProduct[i-1] * postProduct[i+1]
	}
	return res
}

/**
 * @Description: 221. 最大正方形 中等
 * @Keyword: 动态规划,右下角
 * @Author: kami
 * @Date: 2022/6/25 20:05
 **/
func maximalSquare(matrix [][]byte) int {
	dp := make([][]int, len(matrix))
	maxSide := 0
	for i := 0; i < len(matrix); i++ {
		dp[i] = make([]int, len(matrix[i]))
		for j := 0; j < len(matrix[i]); j++ {
			dp[i][j] = int(matrix[i][j] - '0')
			if dp[i][j] == 1 && maxSide == 0 {
				maxSide = 1
			}
		}
	}

	for i := 1; i < len(matrix); i++ {
		for j := 1; j < len(matrix[i]); j++ {
			if dp[i][j] == 1 {
				dp[i][j] = getMin(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
				if dp[i][j] > maxSide {
					maxSide = dp[i][j]
				}
			}
		}
	}

	return maxSide * maxSide
}

/**
 * @Description: 394. 字符串解码 中等
 * @Keyword: 栈，临时字符串
 * @Author: kami
 * @Date: 2022/6/27 13:42
 **/
func decodeString(s string) string {
	var stack []string
	var idx = 0
	for idx < len(s) {
		if s[idx] >= '0' && s[idx] <= '9' {
			var cur []byte
			for idx < len(s) {
				if s[idx] >= '0' && s[idx] <= '9' {
					cur = append(cur, s[idx])
					idx++
					continue
				}
				break
			}
			stack = append(stack, string(cur))
		} else if s[idx] == '[' || (s[idx] >= 'a' && s[idx] <= 'z') {
			stack = append(stack, string(s[idx]))
			idx++
		} else {
			idx++
			sub := []string{}
			for stack[len(stack)-1] != "[" {
				sub = append([]string{stack[len(stack)-1]}, sub...)
				stack = stack[:len(stack)-1]
			}
			// 弹出 【
			stack = stack[:len(stack)-1]
			repTime, _ := strconv.Atoi(stack[len(stack)-1])
			// 弹出数字
			stack = stack[:len(stack)-1]
			t := strings.Repeat(getString(sub), repTime)
			stack = append(stack, t)
		}
	}
	return getString(stack)
}
func getString(v []string) string {
	ret := ""
	for _, s := range v {
		ret += s
	}
	return ret
}

/**
 * @Description: 394. 字符串解码 中等
 * @Keyword: 递归
 * @Author: kami
 * @Date: 2022/6/27 13:42
 **/
func decodeString394(s string) string {
	var dfs func(str string, i int) []string
	dfs = func(str string, i int) []string {
		var res string
		var multi int
		for i < len(str) {
			if str[i] >= '0' && str[i] <= '9' {
				multi = multi*10 + int(s[i]-'0')
			} else if str[i] == '[' {
				var tmp = dfs(str, i+1)
				i, _ = strconv.Atoi(tmp[0])
				for multi > 0 {
					res += tmp[1]
					multi--
				}
			} else if str[i] == ']' {
				return []string{strconv.Itoa(i), res}
			} else {
				res += string(str[i])
			}
			i++
		}
		return []string{res}
	}

	return dfs(s, 0)[0]
}

func findKthLargest20240105(nums []int, k int) int {
	return QuickSearch(nums, 0, len(nums)-1, k-1)
}

func QuickSearch(nums []int, left int, right int, k int) int {
	randomIndex := randomPartition20240105(nums, left, right)
	if randomIndex == k {
		return nums[randomIndex]
	} else if randomIndex < k {
		return QuickSearch(nums, randomIndex+1, right, k)
	} else if randomIndex > k {
		return QuickSearch(nums, left, randomIndex-1, k)
	}
	return -1
}

func randomPartition20240105(nums []int, left int, right int) int {
	randomIndex := rand.Intn(right-left+1) + left
	nums[right], nums[randomIndex] = nums[randomIndex], nums[right]
	return partition20240105(nums, left, right)
}

func partition20240105(nums []int, left int, right int) int {
	pivot, pivotIndex := nums[right], right
	for left < right {
		for left < right && nums[left] >= pivot {
			left++
		}
		for left < right && nums[right] <= pivot {
			right--
		}
		if left < right {
			nums[left], nums[right] = nums[right], nums[left]
		}
	}
	nums[pivotIndex], nums[left] = nums[right], nums[pivotIndex]
	return left
}
